#include "string_array.h"
#include<bits/stdc++.h>
using namespace std;

// 实现myStr
myStr::myStr()//无参构造
{
    
}

myStr::myStr(const char* ch)//有参构造
{
    for (int i = 0; ch[i] != '\0'; i++)
    {
        length++;
    }
    data = new char[length + 1];
    for (int i = 0; i < length; i++)
    {
        data[i] = ch[i];
    }
    data[length] = '\0';
}

myStr::~myStr() // 字符串销毁~myStr(),没搞懂为什么释放data会报错
{
    length=0;
}

void myStr::kmp_next()//kmp辅助数组next的计算
{
    next = new int[length + 1];
    int i = 0;
    next[0] = -1;
    int j = -1;
    while (i < length - 1)
    {
        if (j == -1 || data[i] == data[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
    for (int i = 0; i < length; i++)
        next[i]++;
    return;
};

void myStr::kmp_nextVal()//kmp辅助数组nextVal的计算
{
    nextVal = new int[length + 1];
    int i = 0;
    nextVal[0] = -1;
    int j = -1;
    while (i < length - 1)
    {
        if (j == -1 || data[i] == data[j])
        {
            i++;
            j++;
            if (data[i] != data[j])
                nextVal[i] = j;
            else
                nextVal[i] = nextVal[j];
        }
        else
            j = nextVal[j];
    }
    for (int i = 0; i < length; i++)
        nextVal[i]++;

    return;
};


//实现myStr的友元函数，改进KMP算法的字符串匹配算法int kmpMatch(const myStr& S, const myStr& T)，目标串S和模式串T，求T在S中的位置。匹配失败返回-1，匹配成功返回匹配位置（字符串的位置从1开始）
int kmpMatch(const myStr& S, const myStr& T)
{
    int i = 1, j = 1;
    while (i <= S.length && j <= T.length)
    {
        if (j == 0 || S.data[i - 1] == T.data[j - 1])
        {
            i++;
            j++;
        }
        else
            j = T.next[j - 1];
    }
    if (j > T.length)
        return i - T.length;
    return -1;
};

//实现myStr的友元函数，改进KMP算法的字符串匹配算法int kmpMatch(const myStr& S, const myStr& T)，目标串S和模式串T，求T在S中的位置。匹配失败返回-1，匹配成功返回匹配位置（字符串的位置从1开始）
int simpleMatch(const myStr& S, const myStr& T)
{

    int i = 1;
    int j = 1;
    while (i <= S.length && j <= T.length)
    {
        if (S.data[i - 1] == T.data[j - 1])
        {
            ++i;
            ++j;
        }
        else
        {
            i = i - j + 2;
            j = 1;
        }
    }
    if (j > T.length)
    {
        return i - T.length;
    }
    else
        return -1;
};

//实际上就是一个加了初始位置的暴力匹配函数
int myStr::Index(myStr s1, myStr s2, int pos)
{

    int i = pos;
    int j = 1;
    while (i <= s1.length && j <= s2.length)
    {
        if (s1.data[i - 1] == s2.data[j - 1])
        {
            ++i;
            ++j;
        }
        else
        {
            i = i - j + 2;
            j = 1;
        }
    }
    if (j > s2.length)
    {
        return i - s2.length;
    }
    else
        return 0;
}

////实现myStr的友元函数，串的替换bool replaceStr(myStr& S, const int& start, const myStr& T, const myStr& V)，即要求在主串S中，从位置start开始查找是否存在子串T，若主串S中存在子串T，则用子串V替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回0， start取值从1开始
bool replaceStr(myStr& S, const int& start, const myStr& T, const myStr& V)
{
    int index = S.Index(S, T, start);
    if (index==0)
    {
        return 0;
    }
        
    myStr new_s;
    new_s.length = S.length + (V.length - T.length);
    new_s.data = (char*)malloc((new_s.length) * sizeof(char));//这里做个标记
    
    for(int i=0;i<=index-2;i++)
    {
        new_s.data[i]=S.data[i];
    }
    for(int i=index-1;i<=index+V.length-2;i++)
    {
        new_s.data[i]=V.data[i-(index-1)];
    }
    for(int i=index+V.length-1;i<new_s.length;i++)
    {   
        new_s.data[i]=S.data[i-V.length+T.length];
    }

    S=new_s;
    return 1;
}

void myStr::print() // 字符串输出void print()
{
    for (int i = 0; i < this->length; i++)
        cout << this->data[i];

    cout << endl;
}

void myStr::printNext()
{
    for (int i = 0; i < length; i++)
        cout << next[i];
    cout << endl;
}

void myStr::printNextVal()
{
    for (int i = 0; i < length; i++)
        cout << nextVal[i];
    cout << endl;
}




//实现稀疏矩阵类
bool compare(matrixNode a,matrixNode b)//用于sort的比较函数
{
    if(a.row!=b.row)
    {
        return a.row<b.row;
    }
    return a.col<b.col;
}

myMatrix::myMatrix(const int& rNum, const int& cNum, const int& nNum, const int* n)//参数依次为行数、列数、三元组元素个数、三元组初始化数据，数组元素为3的倍数，每3个数一组，分别为（row，col，value）
{
    rowNum=rNum;
    colNum=cNum;
    nodeNum=nNum;
    nodeList=new matrixNode[nNum];
    for(int i=0,p=0;i<3*nNum;i=i+3,p++)
    {
        nodeList[p].row=n[i];
        nodeList[p].col=n[i+1];
        nodeList[p].value=n[i+2];
    }
    sort(nodeList,nodeList+nodeNum,compare);//进行一下按行排序

}

myMatrix::myMatrix()
{
    rowNum=0;
    colNum=0;
    nodeNum=0;
    nodeList=NULL;//初始化为0就行
}

myMatrix::myMatrix(const myMatrix& s)
{
    rowNum=s.rowNum;
    colNum=s.colNum;
    nodeNum=s.nodeNum;
    nodeList=new matrixNode[nodeNum];
}

myMatrix::~myMatrix()//销毁稀疏矩阵
{
    rowNum=0;
    colNum=0;
    nodeNum=0;
    delete [] nodeList;
}

//下面是一个比较偷懒的做法,使用sort进行快排,直接达到转置的目的
/*
void myMatrix::FastTransposeSMatrix(myMatrix& t)//把矩阵转置,并存在t上
{
    t.rowNum=rowNum;//先进行复制
    t.colNum=colNum;
    t.nodeNum=nodeNum;
    t.nodeList=new matrixNode[t.nodeNum];
    for(int i=0;i<nodeNum;i++)
    {
        t.nodeList[i]=nodeList[i];
    }

    swap(t.rowNum,t.colNum);//不要忘记交换整个矩阵的行数和列数
    for(int i=0;i<t.nodeNum;i++)//在对t进行转置
    {
        swap(t.nodeList[i].row,t.nodeList[i].col);//对每一个元素的行号和列号进行交换
    }
    sort(t.nodeList,t.nodeList+nodeNum,compare);//进行重新排序
}
*/

//这是一个真正的快速转置做法(应该来说是sort函数底层的原理)
void myMatrix::FastTransposeSMatrix(myMatrix& n)
{
    n.rowNum = colNum;
    n.colNum = rowNum;
    n.nodeNum = nodeNum;
    n.nodeList = new matrixNode[n.nodeNum];

    int num[100001], cpot[100001];//num[i]是第i列的非零元个数,cpot[i]表示转置后第i列的第一个非零元素在n.nodeList中的起始位置
    memset(num, 0, sizeof(num));
    memset(cpot, 0, sizeof(cpot));

    for (int i = 0; i < nodeNum; i++)//计算每列的非零元素数量
    {
        num[nodeList[i].col]++;
    }
    cpot[0] = 0;
    for (int i = 1; i < colNum; i++)
    {
        cpot[i] = cpot[i - 1] + num[i - 1];//
    }
        
    int p = 0, q = 0;
    for (int i = 0; i < nodeNum; i++)
    {
        p = nodeList[i].col;
        q = cpot[p];
        n.nodeList[q].row = nodeList[i].col;
        n.nodeList[q].col = nodeList[i].row;
        n.nodeList[q].value = nodeList[i].value;
        cpot[p]++;
    }
}

void myMatrix::printMatrix()
{
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for (int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}
